package com.copa.l543;

/**
 * @author copa
 * @createDate 2022-08-08 17:05
 * @function 深度优先遍历
 */
public class Test1 {

    // 这个定义当前直径最大值，每次左右树算出来都要汇总
    private int result = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return result;
    }

    private int dfs(TreeNode root) {
        int left = 0;
        int right = 0;
        if (root.left != null) {
            left = dfs(root.left);
        }
        if (root.right != null) {
            right = dfs(root.right);
        }
        // 计算当前节点左右子树直径总数最大值
        result = Math.max(result, left + right);
        // 计算父节点深度
        return Math.max(left, right) + 1;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        System.out.println(new Test1().diameterOfBinaryTree(root));
    }
}
